package b;

import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;

public class 复杂链表拷贝 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        //
        Node t1=head;
        while(t1!=null){
            map.put(t1,new Node(t1.val));
            t1=t1.next;
        }
        //
        Node t2=head;
        while(t2!=null){
            Node cur=map.get(t2);//注意：直接get地址Node，而不是val
            cur.next=map.get(t2.next);
            cur.random=map.get(t2.random);
            t2=t2.next;
        }
        //
        return map.get(head);
    }
}
